/**
 * Exercise 3.27
 * -------------------
 * Given pointers `x` and `t` to nodes on a circular list,
 * write a code fragment that moves the node following `t` to the position
 * following the node following `x` on the list.
 * -------------------------------------------------------------------------
 * 
 * 假设原环形列表为`...→x→A→...→t→B→...`，
 * 操作后应该变成`...→x→A→B→...→t→...`。
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int Item;
typedef struct node *link;

struct node {
    Item item;
    link next;
};

void move(link x, link t);
void test_move_adjacent();
void test_move_non_adjacent();
void test_single_node();

int main(int argc, char **argv) {
    test_move_adjacent();
    test_move_non_adjacent();
    test_single_node();
    return 0;
}

/**
 * move
 * ---------------
 * 假设原环形列表为`...→x→A→...→t→B→...`，
 * 操作后应该变成`...→x→A→B→...→t→...`。
 */
void move(link x, link t) {
    assert(x != NULL);
    assert(t != NULL);
    
    // 获取待移动的节点 B = t->next
    link B = t->next;
    if (B == t) return; // t 是唯一节点，无需操作
    
    // 将 B 从原位置移除
    t->next = B->next;
    
    // 将 B 插入到 x 的下一个节点 A 之后
    link A = x->next;

    B->next = A->next;
    A->next = B;
}

void test_move_adjacent() {
    link x = malloc(sizeof(struct node));
    link A = malloc(sizeof(struct node));
    link t = malloc(sizeof(struct node));
    link B = malloc(sizeof(struct node));
    
    // 构建循环链表 x→A→t→B→x
    x->next = A;
    A->next = t;
    t->next = B;
    B->next = x;
    
    move(x, t);
    
    assert(x->next == A);     // x → A
    assert(A->next == B);     // A → B
    assert(B->next == t);     // B → t
    assert(t->next == x);     // 循环闭合
    
    free(x); free(A); free(t); free(B);
}

void test_move_non_adjacent() {
    link x = malloc(sizeof(struct node));
    link A = malloc(sizeof(struct node));
    link B = malloc(sizeof(struct node));
    link t = malloc(sizeof(struct node));
    link C = malloc(sizeof(struct node));
    link D = malloc(sizeof(struct node));
    
    // 构建循环链表 x→A→B→t→C→D→x
    x->next = A;
    A->next = B;
    B->next = t;
    t->next = C;
    C->next = D;
    D->next = x;
    
    move(x, t);
    
    assert(x->next == A);     // x → A
    assert(A->next == C);     // A → C（C 是 t 的原下一个节点）
    assert(C->next == B);     // C → B（B 是原 A 的下一个节点）
    assert(t->next == D);     // t → D
    
    free(x); free(A); free(B); free(t); free(C); free(D);
}

void test_single_node() {
    link t = malloc(sizeof(struct node));
    t->next = t;
    
    move(t, t); // 无操作
    assert(t->next == t);
    
    free(t);
}